package biteHomework._11_01;

import java.util.Arrays;
//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
public class H_07 {
    public static void main(String[] args) {
        int[] arr = {2,2,1,1,1,2,2};
        System.out.println(many(arr));
    }
    public static int many(int[] arr){
        int[] count = new int[arr.length]; //将每个数字出现的次数保存在该数组中
        int[] values = new int[arr.length]; //将该数字与次数下标对应保存到此数组中
        Arrays.fill(count,1);//默认每个数字出现一次
        Arrays.sort(arr);//从小到大排序
        for (int i = 0, j = 0; i < arr.length - 1; i++) {
            if(arr[i] == arr[i+1]){ //如果前一个数字等于后一个数字，则该数字出现的次数加1，并记录该数字
                count[j]++;
                values[j] = arr[i];
            } else {
                j++;// 否则记录下一个数字
            }
        }
        int max = 0;//默认最大次数为0
        int res = -1;//默认结果为-1
        for (int i = 0; i < count.length - 1; i++) { //循环遍历count数组
            if(count[i] > max && count[i] > (arr.length / 2)){
                max = count[i]; //如果有最大次数并且大于数组长度的一半 //更新最大次数
                res = values[i];//并且刷新与之对应下标的values数组的值
            }
        }
        return res; //求出最大次数对应的元素值并返回
    }
}
